Computers in different enterprise networks may communicate with each other over a secure virtual private network (VPN). Key servers associated with the VPN generate and distribute cryptographic keys and policies to network elements in the VPN so that the network elements are able to perform cryptographic operations on network traffic based on the keys and policies. The key servers also periodically refresh the keys and policies in the network elements using a rekey service. The key servers may include a redundant or failover key server that use a consistency service (in addition to the rekey service) to synchronize their keys and polices if a primary key server fails. The rekey and consistency services are examples of key distribution processes or protocols.
To increase security over that provided by a first VPN, a customer may employ a second VPN that performs cryptographic/security operations independently of the first VPN to super-encrypt data packets that traverse both VPNs. Conventionally, the first and second VPNs employ separate, independent first and second rekey services and independent first and second consistency services, respectively.